package week_04;

/**
 * 704. 二分查找
 * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
 * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
 *
 *
 * 示例 1:
 *
 * 输入: nums = [-1,0,3,5,9,12], target = 9
 * 输出: 4
 * 解释: 9 出现在 nums 中并且下标为 4
 * 示例 2:
 *
 * 输入: nums = [-1,0,3,5,9,12], target = 2
 * 输出: -1
 * 解释: 2 不存在 nums 中因此返回 -1
 */
public class BinarySearch_704 {
    public int search(int[] nums, int target) {
        // 模版1.1
        int n=nums.length;
        int left =0;
        int right=n;
        while(left<right){
            int mid =(left+right)>>1;
            System.out.println(mid+":"+left+":"+right);
            if(nums[mid]==target){
                System.out.println(mid+":"+target);
                return mid;
            }else if(nums[mid]>target){
                right=mid;
            }else{
                left =mid+1;
            }
        }
        // 最后循环一定停止在left==right
        return -1;
    }

    public int search_1(int[] nums, int target) {
        // 模版1.1
        int n=nums.length;
        int left =0;
        int right=n-1;
        while(left<=right){
            int mid =(left+right)>>1;
            System.out.println(mid+":"+left+":"+right);
            if(nums[mid]==target){
                System.out.println(mid+":"+target);
                return mid;
            }else if(nums[mid]>target){
                right=mid-1;
            }else{
                left =mid+1;
            }
        }
        return -1;
    }

}
